package com.wtgroup.demo.leetcode.org_bytedance;

import com.wtgroup.demo.common.util.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 103. 二叉树的锯齿形层序遍历
 * <p>
 * 1. 递归实现
 * 2. 广度优先遍历
 *
 * @author 60906
 * @date 2021/5/6 19:22
 */
public class Q_二叉树的锯齿形层序遍历 {

    /**
     * 我自己写的
     * 容器使用臃肿, 一个双端队列即可
     */
    class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            // 自左向右遇到的节点放进来, 取左孩子压右栈 -->
            Stack<TreeNode> leftStack = new Stack<>();
            // 自右向左遇到的节点放进来, 取有孩子压左栈 <--
            Stack<TreeNode> rightStack = new Stack<>();
            List<List<Integer>> vessel = new ArrayList<>();
            leftStack.push(root);

            while (!leftStack.isEmpty() || !rightStack.isEmpty()) {
                List<Integer> left2right = new ArrayList<>();
                while (!leftStack.isEmpty()) {
                    TreeNode cur = leftStack.pop();
                    if (cur == null) continue;
                    left2right.add(cur.val);
                    rightStack.push(cur.left);
                    rightStack.push(cur.right);
                }
                if (!left2right.isEmpty()) vessel.add(left2right);
                List<Integer> right2left = new ArrayList<>();
                while (!rightStack.isEmpty()) {
                    TreeNode cur = rightStack.pop();
                    if (cur == null) continue;
                    right2left.add(cur.val);
                    leftStack.push(cur.right);
                    leftStack.push(cur.left);
                }
                if (!right2left.isEmpty()) vessel.add(right2left);
            }

            return vessel;
        }
    }

    /*
    LC 广度优先遍历思路更简洁
    每层用双端队列, 由标记变量标记左到右还是右到左, 从而, 元素是放到队尾还是队头.


     */
}
